# 验证栈序列： 


# 自己写出来的，直接模拟
class Solution:
    def validateStackSequences(self, pushed: list, popped: list) -> bool:
        """
            直接模拟解法： 这两个栈，其实就是模拟的进栈出栈的过程。 我们只需要再定义一个栈，按照上面的出栈进栈，若最后栈为空，则正确
            定义双指针， i 遍历 pushed, j 遍历 poped.  判断定义栈中是否和 poped相同，不相同就添加
        """
        stack = list()
        i = j = 0
        n = len(popped)
        while j < n:
            if not stack or stack[-1] != popped[j]:
                # 如果当前栈顶不等于 poped的当前元素，而i右走到了头，那么只能是错误，栈不可能为空了
                if i >= n: return False
                stack.append(pushed[i])
                i += 1
            elif stack[-1] == popped[j]:
                stack.pop()
                j += 1
            
        return not stack